package com.wujunshen.algorithm.leetcode.divide.conquer;

import java.util.ArrayList;
import java.util.List;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/30 22:19<br>
 */
public class 给表达式添加运算符 {
    public List<String> addOperators(String num, int target) {
        List<String> resultList = new ArrayList<>();
        if (num.length() == 0) {
            return resultList;
        }

        dfs(resultList, new StringBuilder(), num, target, 0, 0, 0, 0);

        return resultList;
    }

    private void dfs(List<String> resultList, StringBuilder sb, String num, long target, int index, long pre,
                     long curr, long value) {
        if (index == num.length()) {
            if (value == target && curr == 0) {
                resultList.add(sb.substring(1));
            }
            return;
        }

        // 溢出了
        if ((curr * 10 + num.charAt(index) - '0') / 10 != curr) {
            return;
        }

        curr = curr * 10 + num.charAt(index) - '0';
        String currStr = String.valueOf(curr);
        int currSize = currStr.length();

        // 啥也不加
        // 等于0的时候不能啥也不加，比如给定105，会出现1*05这种结果
        if (curr > 0) {
            dfs(resultList, sb, num, target, index + 1, pre, curr, value);
        }

        // 添加 +
        // 第一个符号只能加 + ，后面计算结果的时候把它去掉
        sb.append("+").append(curr);
        dfs(resultList, sb, num, target, index + 1, curr, 0, value + curr);
        sb.delete(sb.length() - currSize - 1, sb.length());

        if (sb.length() > 0) {
            // 添加 -
            sb.append("-").append(curr);
            dfs(resultList, sb, num, target, index + 1, -curr, 0, value - curr);
            sb.delete(sb.length() - currSize - 1, sb.length());

            // 添加 *
            sb.append("*").append(curr);
            dfs(resultList, sb, num, target, index + 1, curr * pre, 0, value - pre + (curr * pre));
            sb.delete(sb.length() - currSize - 1, sb.length());
        }
    }
}
